package Tree.Recursive;

import Utils.TreeNode;

/**
 * 另一个树的子树
 * Lettcode 572: https://leetcode-cn.com/problems/subtree-of-another-tree/
 */
public class isSubTree {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) {
            return false;
        }
        return isSame(s, t) || isSame(s.left, t) || isSame(s.right, t);
    }

    private boolean isSame(TreeNode input, TreeNode target) {
        if (input == null && target == null) {
            return true;
        }
        if (input == null || target == null) {
            return false;
        }
        if (input.val != target.val) {
            return false;
        }
        return isSame(input.left, target.left) && isSame(input.right, target.right);
    }
}
